package niuke.wangyi;

/**
 * Created by hua66 on 2017/9/16.
 */
public class aewf {
	public static void main(String[] args) {
		long[] arr = new long[] { 1L, 2L, 3L, 4L, 5L };
		long m = 10L;
		System.out.println(maxHit(arr, m));
		System.out.println(maxHitDp(arr, m));
	}

	public static long maxHit(long[] arr, long m) {
		if (m < 0 || arr == null || arr.length == 0)
			return -1;
		if (m == 0)
			return 0;
		return process(arr, 0, m);
	}

	public static long process(long[] arr, int cur, long m) {
		if (cur == arr.length)
			return m == 0 ? 1 : -1;
		if (m == 0)
			return 1;
		else if (m < 0)
			return -1;
		return Math.max(arr[cur] * process(arr, cur + 1, m - arr[cur]), process(arr, cur + 1, m));
	}

	public static long maxHitDp(long[] arr, long m) {
		long[][] dp = new long[arr.length + 1][(int) (m + 1)];
		for (int i = 0; i < m + 1; i++) {
			dp[arr.length][i] = -1;
		}
		for (int i = 0; i < arr.length + 1; i++) {
			dp[i][0] = 1;
		}

		for (int i = arr.length - 1; i >= 0; i--) {
			long K = arr[i];
			for (int j = 1; j < m + 1; j++) {
				dp[i][j] = Math.max(((j - K) < 0 ? -1 : (K * dp[i + 1][(int) (j - K)])), dp[i + 1][j]);
			}
		}
		return dp[0][(int) m];
	}
}
